package 二分;

import java.util.Arrays;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/2/12 15:28
 */
public class leetcode6355统计公平数对的数目 {

    /*
      贴 一个 arignote 的代码
      真的 看不懂! 是怎么 做到的!
     时间复杂度 还是 N * LogN
     */
    class Solution {

        public long countFairPairs(int[] nums, int lower, int upper) {
            Arrays.sort(nums);
            long count = 0;
            for (int i = 0, j = nums.length - 1, k = nums.length - 1; i < nums.length; i++) {
                for (; j >= 0 && nums[i] + nums[j] >= lower; j--) {
                }
                for (; k >= 0 && nums[i] + nums[k] > upper; k--) {
                }
                count += k - j - (i > j && i <= k ? 1 : 0);
            }
            return count / 2;
        }
    }

    /*
     先解决 一个 引申的 问题:
     给出 数组 nums[], 求 0  <= i < j < n ,的范围 内 nums[i] + nums [j] <= upper 的 数对, 个数?
     一:
      排序 + 滑动窗口And双指针.双指针 :
      注意一下 这个思想!

      二:
      排序 + 二分: (跟下面的解法 是 一致的 ,还是要 理解枚举的范围) 代码同下面的解法

     */
    public int solutionDoublePointer(int nums[],int upper){
        return 0;
    }




    /*
    如果 不知道 一个 题,的解法,
    先把 暴力的 解法 写出来, 然后看,
    怎么 样 才能 凑成 能够 ac 的时间复杂度

    ===
    显然 暴力 是 两层 for 循环
    O(N ^ 2)

    ==
    NLogN 可以 过
    这个 又可以分成 两种:
    ①: N * LogN 先 for 循环 + 后二分

    ② LogN *  N  : 先 二分 + for 循环!
     二分 答案 类似的题目, 好像有 点类似于这种思想
    ==
    O(N) 更加 可以 过, 但是 O(N) 的 算法, 可不容易 就能写出来!

     */

    /*
        注意 一个现象:
        eg:
        1 2 5 7 ... 9
        假设 我们 要求 <= 7 (x) 的个数,
        方法① :
            求出满足 <= 7 (x) 的最右边的 下标 index   ( index - 0 + 1 就是 <= 7 的 个数)
            但是 这种方法存在 一个 问题, x 或者 说 7  的 存在与否, 对结果 是 有影响的
            Ⅰ :  如果 7 存在, 则 返回的 是 7 的下标
            Ⅱ : 如果 7 不存在, 返回的则是  5 的下标
            你发现 情况 并不唯一!
            这可能是 solutionOne 失败的 方法!
        方法 ②:
            我们 反着算, 求  <=7 的个数, 我们直接
            算  > 7 的 最左边的 下标, 直接就是 <= 7 的个数
            而且 这种 不会出现 讨论 的 分类情况,
            无论 7 (x) 是否存在, 对结果没有任何的 影响
            所以 这种方式 才是 这个题的 正确的 方式 之一!

    ===========

      <= upper - nums[j] 的 个数   等价于  > upper - nums[j] 的下标
      < lower - nums[j] 的个数   等价于  >= lower - nums[j] 的下标

      但是 这里 要注意 一下 ,二分的 范围, 不是 整个 数组, 这里 怎么 理解 , 很抽象!
     */

    public long solutionTwo(int[] nums,int lower,int upper){
        long  ans = 0;
        Arrays.sort(nums);
        for(int i = 0;i<  nums.length ;i++){
            int l = getLeft(nums,lower - nums[i],i);
            int r = getLeft(nums,upper - nums[i] + 1,i);
            ans += r - l;
        }
        return ans;
    }
    public int getLeft(int[] nums,int aim,int right){
        int l = 0,r = right;
        while(l < r){
            int mid = l + r >> 1;
            if(nums[mid] < aim){
                l = mid + 1;
            }
            else{
                r = mid;
            }
        }
        return l;
    }





    /*
      下面 是个 失败的 版本.
      思虑 是错的
      为什么 是错的 , 主要是 二分的范围, 不是 整个 数组 , 而是 一个 范围 内的二分!
     */
    public long solutionOne(int nums[] ,int lower,int upper){
        long ans = 0;

        for(int i = 0;i < nums.length;i++){
            int left = getLeft(lower - nums[i],nums);
            int right = getRight( upper - nums[i],nums);
            ans += left == -1 || right == -1 ? 0 : right - left + 1;
        }
        return ans;
    }


    public static int getRight(int aim,int nums[]){
        int l = 0,r = nums.length - 1;
        int idx = -1;
        while(l < r){
            int mid = l + r + 1 >> 1;
            if(nums[mid] > aim){
                r = mid - 1;
            }
            else{
                idx = mid;
                l = mid;
            }
        }
        return l;
    }
    public int getLeft(int aim,int nums[]){
        int l = 0,r = nums.length - 1;
        int idx = -1;
        while(l < r){
            int mid = l + r >> 1;
            if(nums[mid] < aim){
                l = mid + 1;
            }
            else{
                idx = mid;
                r = mid;
            }
        }
        return idx;
    }

    public static void main(String[] args) {
//        int nums[] = {0,1,7,4,4,5};
        int nums[] = {1,7,9,2,5};
        int lower = 11,upper = 11;
        long l = new leetcode6355统计公平数对的数目().solutionOne(nums, lower, upper);
        System.out.println(l);

    }




    /*
     暴力
     这个 不用 想的, 根据这个 数据范围,肯定 会超时!
     */
    public long solution(int nums[],int lower,int upper){
        long ans = 0;
        for(int i = 0;i < nums.length;i++){
            for(int j = i + 1;j < nums.length;j++){
                int sum = nums[i] + nums[j];
                if(sum <= upper && sum >= lower){
                    ans++;
                }
            }
        }
        return ans;
    }

}
